package leetcode.top100;

/**
 * 乘积最大子数组
 * @since 2019/12/27 0027 下午 9:34
 */
public class Code152_MultiMaxSubArray {
    public static void main(String[] args) {
        int[] nums = {2,3,-2,4};
        System.out.println(maxProduct(nums));
    }
    public static int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return process2(nums);
    }

    /**
     * 方式2：从问题本质分析
     *
     * 分析见笔记
     */
    private static int process2(int[] nums) {
        int max = nums[0];
        int res = 1;
        //正序遍历，包含所有是正数和偶数个负数 以及 遍历到最后一个负数之前的情况
        for (int i = 0; i < nums.length; i++) {
            res *= nums[i];
            max = Math.max(max,res);
            if(nums[i] == 0){
                res = 1;
            }
        }
        res = 1;
        //逆序遍历，包含保留0-第一个负数的情况
        for (int i = nums.length - 1; i >= 0; i--) {
            res *= nums[i];
            max = Math.max(max,res);
            if(nums[i] == 0){
                res = 1;
            }
        }
        return max;
    }
    //方式1：暴力遍历
    private  int m1(int[]nums){
        int res = nums[0];
        for(int i=0 ; i < nums.length; i++){
            int temp = 1;
            for(int j = i ; j < nums.length ; j++){
                temp *= nums[j];
                res = Math.max(res,temp);
            }
        }
        return res;
    }

    //方式3：dp
    public int maxProduct3(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        int[] dpMax = new int[n];
        dpMax[0] = nums[0];
        int[] dpMin = new int[n];
        dpMin[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < n; i++) {
            dpMax[i] = Math.max(dpMin[i - 1] * nums[i], Math.max(dpMax[i - 1] * nums[i], nums[i]));
            dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(dpMax[i - 1] * nums[i], nums[i]));
            max = Math.max(max, dpMax[i]);
        }
        return max;
    }
//    当然，动态规划的老问题，我们注意到更新 dp[i] 的时候，我们只用到 dp[i-1] 的信息，再之前的信息就用不到了。
//    所以我们完全不需要一个数组，只需要一个变量去重复覆盖更新即可。

    public int maxProduct4(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int dpMax = nums[0];
        int dpMin = nums[0];
        int max = nums[0];
        for (int i = 1; i < n; i++) {
            //更新 dpMin 的时候需要 dpMax 之前的信息，所以先保存起来
            int preMax = dpMax;
            dpMax = Math.max(dpMin * nums[i], Math.max(dpMax * nums[i], nums[i]));
            dpMin = Math.min(dpMin * nums[i], Math.min(preMax * nums[i], nums[i]));
            max = Math.max(max, dpMax);
        }
        return max;
    }

}
